//
//  LinkListSolution.cpp
//  leetcode
//
//  Created by Ellie on 2021/1/31.
//  Copyright © 2021 Ellie. All rights reserved.
//

#include "LinkListSolution.hpp"
#include "Helper.h"

using namespace std;

ListNode* LinkListSolution::insertnode(ListNode* head, int value)
{
    if(head == nullptr)
    {
        head = new ListNode(value);
        head->next = nullptr;
        return head;
    }
    // just find and insertion
    ListNode dummy(0);
    ListNode* pre = &dummy;
    dummy.next = head;
    
    while(pre->next != nullptr && (pre->next)->val <= value)
    {
        pre = pre->next;
    }
    ListNode* cur = new ListNode(value);
    cur->next = pre->next;
    pre->next = cur;
    return dummy.next;
}

ListNode* LinkListSolution::findnode(ListNode* head, int value)
{
    if(head == nullptr)
        return nullptr;
    ListNode* cur = head;
    while(cur != nullptr)
    {
        if(cur->val == value)
            return cur;
    }
    return nullptr;
}

// 后续遍历 反向打印链表
// 前序遍历 正向打印链表
// 特殊的二叉树遍历方法
void LinkListSolution::reversePrint(ListNode* head, vector<int>& result)
{
    if(head == nullptr)
        return;
    reversePrint(head->next, result);
    result.push_back(head->val);
}


// 可以使用哨兵节点一般化链表的方法，保证任何链表都有HeadNode
// 针对head的处理可以更简洁一点，while处理head，知道head->val != val 进到正式的删除操作
// 这里没考虑delete释放内存操作
// 头部节点+重复相邻节点的case
ListNode* LinkListSolution::removeElements(ListNode* head, int val)
{
    if(head == nullptr)
        return head;
    ListNode* pre = head;
    ListNode* cur = head;
    while(cur != nullptr)
    {
        ListNode* nextnode = cur->next;
        if(cur->val == val)
        {
            if(cur == head)
                head = nextnode;
            else
                pre->next = nextnode;
        }
        else
            pre = cur;
        cur = nextnode;
    }
    return head;
    
    /* 更简洁的方法，删除指定的元素
     while(head != nullptr && head->val == val)
        head = head->next;
     
     if(head == nullptr)
        return head;
     
     ListNode* pre = head;
     ListNode* cur = head;
     
     while(cur != nullptr)
     {
         ListNode* nextNode = cur->next;
         if(cur->val == val)
            pre->next = nextNode;
         else
            pre = cur;
         cur = nextNode;
     }
     return head;
     */
}

// 找不到前驱节点，跳过该节点，将该节点的值改为下一个节点的值然后跳过
void LinkListSolution::deleteNode(ListNode* node)
{
    if(node == nullptr)
        return;
    node->val = (node->next)->val;
    node->next = node->next->next;
}

ListNode* LinkListSolution::middleNode(ListNode* head)
{
    if(head ==  nullptr)
        return head;
    ListNode* fast = head;
    ListNode* slow = head;
    
    while(fast != nullptr && fast->next != nullptr)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 不改变原来链表的结构，重新生成一个新的链表
ListNode* LinkListSolution::deleteDuplicates(ListNode* head)
{
    if(head == nullptr)
        return nullptr;
    // 亚节点，虚拟节点
    ListNode* dummy = new ListNode(head->val - 1);
    dummy->next = head;
    
    ListNode* pre = dummy;
    ListNode* cur = head;
    
    while (cur != nullptr) {
        int value = cur->val;
        ListNode* temp = cur->next;
        while(temp != nullptr && (temp)->val == value)
        {
            temp = temp->next;
        }
        if(cur->next == temp)
        {
            pre->next = cur;
            pre = cur;
            cur = cur->next;
        }
        else
            cur = temp;
    }
    pre->next = nullptr;
    return dummy->next;
}

// 快慢指针
int LinkListSolution::kthToLast(ListNode* head, int k)
{
    ListNode* fast = head;
    ListNode* slow = head;
    while(k-- > 0)
    {
        fast = fast->next;
    }
    
    while(fast != nullptr)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}

// set inthelper = 0
// 递归操作
ListNode* LinkListSolution::removeNthFromEnd(ListNode* head, int n)
{
    if(head == nullptr)
        return head;
    ListNode dummy(0);
    dummy.next = head;
    ListNode* pre = &dummy;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    while(n -- > 0 && fast != nullptr)
    {
        fast = fast->next;
    }
    
    while(fast != nullptr)
    {
        slow = slow->next;
        pre = pre->next;
        fast = fast->next;
    }
    
    if(slow != nullptr)
        pre->next = slow->next;
    
    return dummy.next;
}

ListNode* LinkListSolution::removeNthFromEndRecursion(ListNode* head, int n)
{
    if(head == nullptr)
        return head;
    head->next = removeNthFromEndRecursion(head->next, n);
    inthelper++;
    if(inthelper == n)
        return head->next;
    return head;
}

ListNode* LinkListSolution::addTwoNumbers(ListNode* l1, ListNode* l2)
{
    if(l1 == nullptr) return l2;
    if(l2 == nullptr) return l1;

    int carry = 0;
    ListNode dummy(0);
    dummy.next = nullptr;
    ListNode* pre = &dummy;

    while(l1 != nullptr || l2 != nullptr || carry != 0)
    {
        int num1 = 0;
        int num2 = 0;
        if(l1 != nullptr)
        {
            num1 = l1->val;
            l1 = l1->next;
        }

        if(l2 != nullptr)
        {
            num2 = l2->val;
            l2 = l2->next;
        }

        int value = num1 + num2 + carry;
        carry = value >= 10 ? 1 : 0;
        
        ListNode* node = new ListNode(value % 10);
        pre->next = node;
        pre = pre->next;
    }

    return dummy.next;
}

ListNode* LinkListSolution::addTwoNumbersReverse(ListNode* l1, ListNode* l2)
{
    if(l1 == nullptr) return l2;
    if(l2 == nullptr) return l1;
    
    stack<int> sk1;
    stack<int> sk2;
    
    while(l1 != nullptr)
    {
        sk1.push(l1->val);
        l1 = l1->next;
    }
    
    while(l2 != nullptr)
    {
        sk2.push(l2->val);
        l2 = l2->next;
    }
    
    ListNode dummy(0);
    dummy.next = nullptr;
    ListNode* pre = &dummy;
    
    int carry = 0;
    while(!sk1.empty() || !sk2.empty() || carry != 0)
    {
        int num1 = 0;
        int num2 = 0;
        if(!sk1.empty())
        {
            num1 = sk1.top();
            sk1.pop();
        }
        
        if(!sk2.empty())
        {
            num2 = sk2.top();
            sk2.pop();
        }
        
        int value = num1 + num2 + carry;
        carry = value >= 10 ? 1 : 0;
        // create new node
        ListNode* node = new ListNode(value % 10);
        node->next = pre->next;
        pre->next = node;
    }
    return dummy.next;
}

// 思路：将K个节点作为新的head返回，同时断开第K-1个节点，同时将尾部和输入的head相接
ListNode*LinkListSolution::rotateRight(ListNode* head, int k)
{
    // 倒数第K个节点作为新的head，接到之前的Head上
    if(k <= 0 || head == nullptr)
               return head;
    
    ListNode dummy(0);
    dummy.next = head;

    ListNode* slow =  head;
    ListNode* fast = head;
    ListNode* pre = &dummy;
    ListNode* end = &dummy;

    int size = 0;
    while(slow != nullptr)
    {
        slow = slow->next;
        size ++;
    }

    k = k % size;
    slow = head;

    // if k == 0 no rotation at all
    if(k == 0)
        return head;

    while(k -- > 0 && fast != nullptr)
    {
        fast = fast->next;
        end = end->next;
    }

    while(fast != nullptr)
    {
        slow = slow->next;
        fast = fast->next;
        pre = pre->next;
        end = end->next;
    }

    pre->next = nullptr;
    end->next = head;
    dummy.next = slow;
    return dummy.next;
}

ListNode* LinkListSolution::mergeTwoLists(ListNode* l1, ListNode* l2)
{
    if(l1 == nullptr) return l2;
    if(l2 == nullptr) return l1;
    
    // Use Dummy Node
    // ListNode* head = nullptr;
    ListNode dummy(0);
    ListNode* pre = &dummy;
    
    while(l1 != nullptr && l2 != nullptr)
    {
        ListNode* addnode = l1;
        if(l1->val <= l2->val)
        {
            addnode = l1;
            l1 = l1->next;
        }
        else
        {
            addnode = l2;
            l2 = l2->next;
        }
//        if(head == nullptr)
//        {
//            head = addnode;
//            pre = addnode;
//        }
//        else
        {
            pre->next = addnode;
            pre = pre->next;
        }
    }
    pre->next = (l1 == nullptr ? l2 : l1);
    // return head;
    return dummy.next;
}

ListNode* LinkListSolution::mergeTwoListsRecursion(ListNode* l1, ListNode* l2)
{
    if(l1 == nullptr) return l2;
    if(l2 == nullptr) return l1;
    ListNode* head = nullptr;
    if(l1->val <= l2->val)
    {
        head = l1;
        head->next = mergeTwoListsRecursion(l1->next, l2);
    }
    else
    {
        head = l2;
        head->next = mergeTwoListsRecursion(l1, l2->next);
    }
    return head;
}

// 每次将合并的链表减半
ListNode* LinkListSolution::mergeKLists(vector<ListNode*>& lists)
{
    if(lists.empty())
        return nullptr;
    int len = lists.size();
    // 总共执行 (len+1)/2轮合并
    // 分而治之的方法
    // 当不知道的时候，可以根据简单的例子确定是否+1
    while(len > 1)
    {
        for(int i=0; i < len/2; i++)
        {
            lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);
        }
        len = (len + 1)/2;
    }
    return lists.front();
}

// Merge K sorted List
ListNode* LinkListSolution::mergeKListsPriorityQuque(vector<ListNode*>& lists)
{
    // 小顶堆，每次取堆的元素都为当前堆的最小值
    priority_queue<ListNode*, vector<ListNode*>, compareNode> que;
    
    // push all lists head to priority_queue
    // 优先级队列
    for(auto l : lists)
    {
        if(l != nullptr)
            que.push(l);
    }
    
    if(que.empty())
        return nullptr;
    
    ListNode* result =  que.top();
    que.pop();
    
    if(result->next != nullptr)
        que.push(result->next);
    
    ListNode* tail = result;
    while(!que.empty())
    {
        tail->next = que.top();
        que.pop();
        tail = tail->next;
        if(tail->next != nullptr)
            que.push(tail->next);
    }
    return result;
}


// 160. 相交链表
ListNode* LinkListSolution::getIntersectionNode(ListNode* headA, ListNode* headB)
{
    if(headA == nullptr || headB == nullptr)
        return nullptr;
    
    ListNode* pA = headA;
    ListNode* pB = headB;
    
    while(pA != pB)
    {
        pA = pA == nullptr ? headB : pA->next;
        pB = pB == nullptr ? headA : pB->next;
    }
    return pA;
}

// fast and slow linknode algorithm
bool LinkListSolution::hasCycle(ListNode* head)
{
    if(head == nullptr)
        return false;
    ListNode* slow = head;
    ListNode* fast = head;
    
    while(fast != nullptr && fast->next != nullptr)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
            return true;
    }
    return false;
}

ListNode* LinkListSolution::detectCycle(ListNode* head)
{
    if(head == nullptr)
        return nullptr;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    bool hascycle = false;
    while(fast != nullptr && fast->next != nullptr)
    {
        fast = fast->next->next;
        slow = slow->next;
        
        if(fast == slow)
        {
            hascycle = true;
            break;
        }
    }
    if(!hascycle)
        return nullptr;
    slow = head;
    while(slow != fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

// Algorithm

// 画图，防止出现编码错误，链表的问题需要心细
ListNode* LinkListSolution::swapPairs(ListNode* head)
{
    if(head == nullptr || head->next == nullptr)
        return head;
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    
    ListNode* cur = head;
    ListNode* nextNode = head->next;
    ListNode* parent = dummy;
    while(cur != nullptr && nextNode != nullptr)
    {
        ListNode* node01 = nextNode->next;
        ListNode* node02 = node01 == nullptr ? nullptr : node01->next;
        
        ListNode* temp = nextNode->next;
        nextNode->next = cur;
        cur->next = temp;
        
        parent->next = nextNode;
        parent = cur;
        
        cur = node01;
        nextNode = node02;
    }
    return dummy->next;
}

// 隔着一个节点进行处理返回
// 1，3
// 3，1
ListNode* LinkListSolution::swapPairsRecursion(ListNode* head)
{
    if(head == nullptr || head->next == nullptr)
        return head;
    ListNode* nextNode = head->next;
    head->next = swapPairsRecursion(nextNode->next);
    nextNode->next = head;
    return nextNode;
}

ListNode* LinkListSolution::reverseList(ListNode* head)
{
    if(head == nullptr)
        return head;
    // pre = nullptr is key
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while(cur != nullptr)
    {
        ListNode* temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

// 返回的节点一定是新的head节点，然后利用递归堆栈过程处理head之前的节点
ListNode* LinkListSolution::reverseListRecursion(ListNode* head)
{
    if(head == nullptr || head->next == nullptr)
        return head;
    ListNode* last = reverseListRecursion(head->next);
    head->next->next = head;
    head->next = nullptr;
    return last;
}

// 反转前N个节点
// 递归翻转，递归返回的节点为新的head，然后利用递归调用的堆栈，开始处理新的head之前的元素，继续后驱
// 需要记录N+1个节点的位置，然后跟着递归从下往上传递上去
ListNode* LinkListSolution::recerseNListRecursion(ListNode* head, int N)
{
    if(N == 1)
    {
        helperSuccessorNode = head->next;
        // 返回的是新的head节点
        return head;
    }
    ListNode* last = recerseNListRecursion(head->next, N --);
    //  same to 翻转整个链表
    head->next->next = head;
    head->next = helperSuccessorNode;
    //
    return last;
}

// 递归
ListNode* LinkListSolution::reverseBetweenRecurion(ListNode* head, int m ,int n)
{
    return nullptr;
}


ListNode* LinkListSolution::reverseBetween(ListNode* head, int m, int n)
{
    if(head == nullptr)
        return head;
    ListNode* cur = head;
    ListNode* pre = nullptr;
    
    while(m > 1)
    {
        pre = cur;
        cur = cur->next;
        
        m--;
        n--;
    }
    
    ListNode* con = pre;
    ListNode* tail = cur;
    
    ListNode* third = nullptr;
    while(n >= 1)
    {
        third = cur->next;
        cur->next = pre;
        pre = cur;
        cur = third;
        n--;
    }
    
    if(con != nullptr)
    {
        con->next = pre;
    }
    else
    {
        head = pre;
    }
    tail->next = cur;
    return head;
}

bool LinkListSolution::isPalindromeSimpleVector(ListNode* head)
{
    if(head == nullptr)
        return nullptr;
    vector<int> vec;
    ListNode* cur = head;
    while(cur != nullptr)
    {
        vec.push_back(cur->val);
        cur = cur->next;
    }
    
    int size = vec.size();
    int i = 0;
    int j = size -1;
    for(; i < j; i++, j--)
    {
        if(vec[i] != vec[j])
            return false;
    }
    return true;
}

bool LinkListSolution::isPalindrome(ListNode* head)
{
    helperFrontNode = head;
    return isPalindromRecursion(head);
}

// 使用递归返回节点的顺序和正序比较
// 参数传入按照原路返回
// 正向和反向遍历的结果一致
bool LinkListSolution::isPalindromRecursion(ListNode* head){
    if(head == nullptr)
        return true;
    bool result = isPalindromRecursion(head->next);
    result = result && helperFrontNode->val == head->val;
    helperFrontNode = helperFrontNode->next;
    return result;
}

bool LinkListSolution::isPaliandromeSlowFast(ListNode* head)
{
    if(head == nullptr)
        return true;
    // 快慢指针方法区分奇数和偶数问题
    // 根据四个节点和三个节点能得到以下结论
    // 奇数：fast != nullptr
    // 偶数：fast == nullptr
    ListNode* fast = head;
    ListNode* slow = head;
    ListNode* first = head;
    while(fast != nullptr && fast->next != nullptr)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 如果是奇数slow需要往前一步
    if(fast != nullptr)
        slow = slow->next;
    
    ListNode* reverse = reverseList(slow);
    while(reverse != nullptr)
    {
        if(reverse->val != first->val)
            return false;
        reverse = reverse->next;
        first = first->next;
    }
    return true;
}
